package com.algrithom.unionfind;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import com.common.model.UnionFind;

/**
 * 684. 冗余连接
 * 
 * @author think
 */
public class Solution5 {
    
    public static void main(String[] args){
        Solution5 solution5 = new Solution5();
        int[][] edges = new int[][]{{1,2},{1,3},{2,3}};
        System.out.println(Arrays.toString(solution5.findRedundantConnection(edges)));
    }
    
    public int[] findRedundantConnection(int[][] edges){
        int len = edges.length;
        UnionFind unionfind = new UnionFind(len);
        int rowLen = edges.length;
        List<Integer> list = new ArrayList<>();
        for (int row = 0; row < rowLen; row++) {
            if (unionfind.find(edges[row][0] - 1) == unionfind.find(edges[row][1] - 1)) {
                list.add(edges[row][0]);
                list.add(edges[row][1]);
            } else {
                unionfind.union(edges[row][0] - 1,edges[row][1] - 1);
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}